/*
 * Copyright (C) 2010 Yury Kudryashov.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package name.kudryashov.collections;

import name.kudryashov.base.Argument;
import name.kudryashov.base.Option;
import name.kudryashov.functions.*;
import name.kudryashov.strings.Joiner;

import java.util.*;

import static name.kudryashov.base.Argument.require;
import static name.kudryashov.base.Argument.requireNotNull;
import static name.kudryashov.base.Option.some;
import static name.kudryashov.collections.Tuple.pair;

public class Iterators {
    private final static EmptyIterator empty = new EmptyIterator();

    /**
     * Returns a new iterator that iterates only over those elements in the given <code>iterator</code>
     * that match the given <code>predicate</code>. If neither element of the given iterator match the filter,
     * then the returned iterator will act as an empty iterator.
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param iterator iterator, not null
     * @param predicate predicate, not null
     * @param <E> type of the element
     * @return the new filtering iterator
     */
    public static <E> Iterator<E> filter(Iterator<E> iterator, Predicate<? super E> predicate) {
        return new FilteringIterator<E>(iterator, predicate);
    }

    /**
     * Returns an empty iterator containing no elements
     * @param <E> type of the elements
     * @return empty iterator
     */
    @SuppressWarnings({"unchecked"})
    public static <E> Iterator<E> empty() {
        return empty;
    }


    /**
     * Returns number of elements remaining in the given iterator. After this call the given iterator
     * will be exhausted, its {@code hasNext()} method will return false.
     * @param iterator iterator, not null
     * @return number of elements remaining in the iterator
     * @throws NullPointerException iterator is null
     */
    public static <E> int size(Iterator<E> iterator) {
        int count = 0;
        while(iterator.hasNext()) {
            iterator.next();
            count++;
        }
        return count;
    }

    /**
     * Returns a new iterator that iterates over elements in the given <code>iterator</code> and maps them
     * to another value using the given function.
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param it iterator, not null
     * @param f mapping function, not null
     * @return the new mapping iterator
     * @throws NullPointerException iterator or function is null
     */
    public static <E, R> Iterator<R> map(Iterator<E> it, Function<? super E, ? extends R> f) {
        return new MappingIterator<E, R>(it, f);
    }

    /**
     * Performs a left fold reduction of the given iterator. After this call the given iterator
     * will be exhausted, its {@code hasNext()} method will return false.
     * @param it iterator to perform left folding for, not null
     * @param initial initial value
     * @param f folding function, not null
     * @param <R> type of the result
     * @return the folding result or initial value if the iterator is empty
     * @throws NullPointerException it or f is null
     */
    public static <E, R> R foldLeft(Iterator<? extends E> it, R initial, Function2<? super E, R, R> f) {
        R result = initial;
        while(it.hasNext()) {
            result = f.apply(it.next(), result);
        }
        return result;
    }

    /**
     * Performs a right fold reduction of the given iterator. After this call the given iterator
     * will be exhausted, its {@code hasNext()} method will return false.
     * @param it iterator to perform right  folding for, not null
     * @param initial initial value
     * @param f folding function, not null
     * @param <R> type of the result
     * @return the folding result or initial value if the iterator is empty
     * @throws NullPointerException it or f is null
     */
    public static <E, R> R foldRight(Iterator<E> it, R initial, Function2<? super E, R, R> f) {
        if(it instanceof ListIterator) {
            foldRight((ListIterator<E>) it, initial, f);
        }
        Deque<E> stack = new ArrayDeque<E>();
        while(it.hasNext()) {
            stack.push(it.next());
        }
        R result = initial;
        while(!stack.isEmpty()) {
            result = f.apply(stack.pop(), result);
        }
        return result;
    }

    // TODO test it
    private static <E, R> R foldRight(ListIterator<E> it, R initial, Function2<? super E, R, R> f) {
        while(it.hasNext()) {
            it.next();
        }
        R result = initial;
        while(it.hasPrevious()) {
            result = f.apply(it.previous(), result);
        }
        return result;
    }

    /**
     * Returns an iterator that performs a flat-map on the given iterator - applies the given function
     * to each of the elements and iterates over the concatenated results of such calls.
     * <p>
     * This iterator does not support {@code remove}.
     * @param it iterator to flatmap, not null
     * @param f function, not null
     * @param <E> type of elements
     * @param <R> type of result
     * @return the flatmapping iterator
     * @throws NullPointerException f or it is null
     */
    public static <E, R> Iterator<R> flatMap(Iterator<E> it, Function<? super E, ? extends Collection<R>> f) {
        return new FlatMappingIterator<E, R>(it, f);
    }

    /**
     * Performs a left reduce on the given iterator. After this call the given iterator
     * will be exhausted, its {@code hasNext()} method will return false.
     * @param it iterator, not null, should have elements
     * @param f reducing function, not null
     * @param <E> type of the elements
     * @return the reduced value
     * @throws IllegalArgumentException {@code it} does not have any elements remaining
     * @throws NullPointerException it or f is null
     */
    public static <E> E reduceLeft(Iterator<? extends E> it, Function2<? super E, E, E> f) {
        require(it.hasNext(), "iterator is empty");
        return foldLeft(it, it.next(), f);
    }

    /**
     * Performs a right reduce on the given iterator. After this call the given iterator
     * will be exhausted, its {@code hasNext()} method will return false.
     * @param it iterator, not null, should have elements
     * @param f reducing function, not null
     * @param <E> type of the elements
     * @return the reduced value
     * @throws IllegalArgumentException {@code it} does not have any elements remaining
     * @throws NullPointerException it or f is null
     */
    public static <E> E reduceRight(Iterator<E> it, Function2<? super E, E, E> f) {
        require(it.hasNext(), "iterator is empty");
        if(it instanceof ListIterator) {
            return reduceRight((ListIterator<E>) it, f);
        }
        Deque<E> stack = new ArrayDeque<E>();
        while(it.hasNext()) {
            stack.push(it.next());
        }
        E acc = stack.pop();
        while(!stack.isEmpty()) {
            acc = f.apply(stack.pop(), acc);
        }
        return acc;
    }

    // TODO test it
    private static <E> E reduceRight(ListIterator<E> it, Function2<? super E, E, E> f) {
        while(it.hasNext()) {
            it.next();
        }
        E acc = it.previous();
        while(!it.hasPrevious()) {
            acc = f.apply(it.previous(), acc);
        }
        return acc;
    }

    /**
     * Returns the iterator that iterates only over the {@code count} first elements of the given iterator.
     * If count is zero or negative, an empty iterator is returned. If count is greater
     * than the number of elements in the iterator, the resulting iterator will iterate over all elements.
     * <p>
     * The returned iterator supports {@link java.util.Iterator#remove()}.
     * @param iterator iterator, not null
     * @param count number of elements to take
     * @param <E> type of elements
     * @return the new iterator
     */
    public static <E> Iterator<E> take(Iterator<E> iterator, int count) {
        return new TakingIterator<E>(iterator, count);
    }

    /**
     * Returns an unmodifiable iterator - the one that does not support {@code remove}.
     * @param iterator iteraror to wrap, not null
     * @param <E> type of elements
     * @return the unmodifiable iterator
     * @throws NullPointerException iterator is null
     */
    public static <E> Iterator<E> unmodifiable(final Iterator<E> iterator) {
        return new Iterator<E>() {
            public boolean hasNext() { return iterator.hasNext(); }

            public E next() { return iterator.next(); }

            public void remove() { throw new UnsupportedOperationException(); }
        };
    }

    /**
     * Returns the iterator that iterates only over the {@code count} last elements of the given iterator.
     * If count is zero or negative, an empty iterator is returned. If count is greater
     * than the number of elements in the iterator, the resulting iterator will iterate over all elements.
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * <p>
     * The returned iterator is not a <code>view</code> of the given iterator - the elements are copied.
     * @param iterator iterator, not null
     * @param count number of elements to take
     * @param <E> type of elements
     * @return the new iterator
     * @throws NullPointerException iterator is null
     */
    public static <E> Iterator<E> takeLast(Iterator<E> iterator, int count) {
        if(!iterator.hasNext() || count <= 0) {
            return empty();
        }
        Deque<E> deque = new ArrayDeque<E>();
        while(iterator.hasNext()) {
            deque.addLast(iterator.next());
            if(deque.size() > count) {
                deque.removeFirst();
            }
        }
        return unmodifiable(deque.iterator());
    }

    /**
     * Returns the iterator that iterates only over the first elements of the given iterator for which the
     * given predicate returns true.
     * If predicate returns false for the first element or if the given iterator is empty, an empty iterator
     * is returned.
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param iterator iterator, not null
     * @param predicate predicate, not null
     * @param <E> type of elements
     * @return the new iterator
     * @throws NullPointerException iterator or predicate is null
     */
    public static <E> Iterator<E> takeWhile(Iterator<E> iterator, Predicate<E> predicate) {
        return new TakingWhileIterator<E>(Argument.requireNotNull(iterator, "iterator"), Argument.requireNotNull(predicate, "predicate"));
    }

    /**
     * Returns the iterator that iterates only over the first elements of the given iterator for which the
     * given predicate returns false.
     * If predicate returns true for the first element or if the given iterator is empty, an empty iterator
     * is returned.
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param iterator iterator, not null
     * @param predicate predicate, not null
     * @param <E> type of elements
     * @return the new iterator
     * @throws NullPointerException iterator or predicate is null
     */
    public static <E> Iterator<E> takeUntil(Iterator<E> iterator, Predicate<E> predicate) {
        return new TakingWhileIterator<E>(Argument.requireNotNull(iterator, "iterator"), Predicates.complement(predicate));
    }

    /**
     * Returns an iterator that cycles infinitely over the elements of the given iterable. For example, calling
     * <code>cycle(Arrays.asList(1, 2, 3)))</code> produces an iterator that iterates over (1, 2, 3, 1, 2, 3...) etc.
     * <p>
     * The returned iterator does not support <code>remove</code>.
     * <p>
     * If an empty iterable is given, an empty iterator is returned
     * <p>
     * WARNING! The iterator returned by this method is infinite!
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param iterable iterable to cycle over, not null
     * @param <E> type of elements in the iterable
     * @return an infinite iterator cycling over the given iterable.
     * @throws NullPointerException iterable is null
     */
    public static <E> Iterator<E> cycle(Iterable<E> iterable) {
        return new CyclingIterator<E>(iterable);
    }

    /**
     * Returns a first element from the given iterator
     * @param it iterator, should not be empty or exhausted
     * @param <E> type of elements
     * @return the first element
     * @throws NullPointerException iterator is null
     * @throws NoSuchElementException iterator is empty
     */
    public static <E> E first(Iterator<E> it) {
        Argument.requireNotNull(it, "it");
        assertHasNext(it);
        return it.next();
    }

    private static <E> void assertHasNext(Iterator<E> it) {
        if(!it.hasNext()) throw new NoSuchElementException();
    }

    /**
     * Returns a first element from the given iterator as an optional value
     * @param it iterator, should not be empty or exhausted
     * @param <E> type of elements
     * @return the first element as Some or None if iterator is empty
     * @throws NullPointerException iterator is null
     */
    public static <E> Option<E> firstO(Iterator<E> it) {
        Argument.requireNotNull(it, "it");
        return it.hasNext() ? some(it.next()) : Option.<E>none();
    }

    /**
     * Returns an iterator iterating over all but the first element.
     * <p>
     * <code>rest(Arrays.asList(1, 2, 3)) = (2, 3)</code>
     * <p>
     * If iterator contains only one element, an empty iterator is returned.
     * @param it iterator, not null
     * @param <E> type of elements
     * @return an iterator iterating over the all but the first element
     * @throws NoSuchElementException iterator is empty
     * @throws NullPointerException iterator is null
     */
    public static <E> Iterator<E> rest(Iterator<E> it) {
        Argument.requireNotNull(it, "it");
        assertHasNext(it);
        return drop(it, 1);
    }

    /**
     * Returns a new iterator that iterates only over those elements in the given <code>iterator</code>
     * that do not match the given <code>predicate</code>. This has an effect of <b>removing</b> the elements
     * that match the predicate. If all the elements of the given iterator match the filter,
     * then the returned iterator will act as an empty iterator.
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param iterator iterator, not null
     * @param predicate predicate, not null
     * @param <E> type of the element
     * @return the new filtering iterator
     * @throws NullPointerException iterator or predicate is null
     */
    public static <E> Iterator<E> remove(Iterator<E> iterator, Predicate<E> predicate) {
        return filter(iterator, Compose.not(predicate));
    }

    // TODO lessen generic burden
    // TODO dropLast, indices, zipWithIndex, group, groupAsMap
    // TODO takeNth, butLast, last, reverse, sort, split, any, all, addAll, retainAll, diff
    // TODO partition
    // TODO getOnly, last
    // TODO forArray - make an iterator, Google states straightforward is slow =)
    // TODO single, peeking, unmodifiable
    // TODO toArray, frequency, histogram

    /**
     * Returns true if the given iterator contains the value that satisfies the given predicate
     * <p>
     * After the call to this method the iterator is on the first element that satisfies the predicate or
     * exhausted if there's no match
     * @param iterator iterator, not null
     * @param predicate predicate, not null
     * @param <E> type of elements
     * @return true if the iterator contains the element, false otherwise
     * @throws NullPointerException iterator or predicate is null
     */
    public static <E> boolean contains(Iterator<E> iterator, Predicate<? super E> predicate) {
        return filter(iterator, predicate).hasNext();
    }

    /**
     * Returns true if the given iterator contains the value that is equal to the given one (in terms of
     * {@code equals})
     * <p>
     * After the call to this method the iterator is on the first element that satisfies the predicate or
     * exhausted if there's no match
     * @param iterator iterator, not null
     * @param what what to look for, not null
     * @param <E> type of elements
     * @return true if the iterator contains the element, false otherwise
     * @throws NullPointerException iterator or predicate is null
     */
    public static <E> boolean containsEqual(Iterator<E> iterator, E what) {
        return contains(iterator, Predicates.equalsTo(what));
    }

    /**
     * Returns true if the given iterator contains the same value (in terms of
     * {@code ==})
     * <p>
     * After the call to this method the iterator is on the first element that satisfies the predicate or
     * exhausted if there's no match
     * @param iterator iterator, not null
     * @param what what to look for, not null
     * @param <E> type of elements
     * @return true if the iterator contains the element, false otherwise
     * @throws NullPointerException iterator or predicate is null
     */
    public static <E> boolean containsSame(Iterator<E> iterator, E what) {
        return contains(iterator, Predicates.sameAs(what));
    }

    /**
     * Returns a first element in the given iterator that satisfies the given predicate. If no elements
     * satisfy the predicate, an exception is thrown
     * @param iterator iterator, not null
     * @param predicate predicate, not null
     * @param <E> type of elements
     * @return first element that satisfies the predicate
     * @throws NullPointerException iterator or predicate is null
     * @throws NoSuchElementException there is no such element in the iterator that satisifies the predicate
     */
    public static <E> E find(Iterator<E> iterator, Predicate<? super E> predicate) {
        return filter(iterator, predicate).next();
    }

    /**
     * Returns a first element in the given iterator that satisfies the given predicate. The element is
     * returned as an {@code Option}.
     * @param iterator iterator, not null
     * @param predicate predicate, not null
     * @param <E> type of elements
     * @return first element that satisfies the predicate as {@code Some} or {@code None} if there is no such element.
     * @throws NullPointerException iterator or predicate is null
     */
    public static <E> Option<E> findO(Iterator<E> iterator, Predicate<? super E> predicate) {
        final Iterator<E> filtered = filter(iterator, predicate);
        return filtered.hasNext() ? some(filtered.next()) : Option.<E>none();
    }

    /**
     * Returns an iterator that interleaves the elements of the given iterators.
     * For example, <code>interleave((1,2,3), (4,5,6))</code> will yield (1,4,2,5,3,6).
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * <p>
     * If iterators are of different size, the longest is truncated.
     * @param iterators iterators to concatenate, not null
     * @return the interleaving iterator or empty one if <code>iterators</code> is empty
     * @throws NullPointerException either <code>iterators</code> or any given iterator is null
     */
    public static <E> Iterator<E> interleave(Iterator<E>... iterators) {
        requireNotNull(iterators, "iterators");
        if(iterators.length == 0) return empty();
        return new InterleavingIterator<E>(iterators);
    }


    /**
     * Returns an iterator that "concatenates" all the given iterators - i.e. iterates over all elements of all the
     * given iterators in order.
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param iterators iterators to concatenate, not null
     * @param <E> type of element
     * @return the concatenating iterator or empty one if <code>iterators</code> is empty
     * @throws NullPointerException either <code>iterators</code> or any given iterator is null
     */
    public static <E> Iterator<E> concat(Iterator<E>... iterators) {
        Argument.requireNotNull(iterators, "iterators");
        return reduceLeft(forArray(iterators), new Function2<Iterator<E>, Iterator<E>, Iterator<E>>() {
            public Iterator<E> apply(Iterator<E> arg1, Iterator<E> arg2) {
                return new JoiningIterator<E>(arg2, arg1);
            }
        });
    }

    /**
     * Returns an iterator that iterates only over the distinct values of the given iterator (skipping
     * duplicates). Duplicates are considered in terms of <code>equals</code> and <code>hashCode</code>.
     * <p>
     * Uses a <code>hash set</code> internally to keep non-duplicate elements so this may prohibit some elements
     * from being GCed if the returned iterator is not released for GC.
     * <p>
     * Requires additional memory proportional to the number of non-duplicates in the given iterator,
     * <p>
     * The returned iterator does not support <code>remove</code>
     * <p>
     * If the given iterator is empty, returns an empty iterator
     * @param iterator iterator to skip duplicates in, not null
     * @param <E> type of elements
     * @return the iterator that skips duplicates of elements in the given iterator
     * @throws NullPointerException if iterator is null
     */
    public static <E> Iterator<E> distinct(Iterator<E> iterator) {
        final Predicate<E> filter = new Predicate<E>() {
            private final Set<E> set = new HashSet<E>();
            public boolean apply(E arg) {
                return set.add(arg);
            }
        };
        return new FilteringIterator<E>(iterator, filter);
    }

    /**
     * Skips the {@code count} elements of the given iterator. Call to this method
     * with "1" advances the iterator by one.
     * If count is greater than the number of elements in the iterator, an exhausted iterator is returned.
     * <p>
     * If count is less than or equals to zero, the iterator is returned intact.
     * @param iterator iterator, not null
     * @param count number of elements to take
     * @param <E> type of elements
     * @return the given iterator skipped by the given count of elements.
     * @throws NullPointerException iterator is null
     */
    public static <E> Iterator<E> drop(Iterator<E> iterator, int count) {
        if(count <= 0) return iterator;
        int left = count;
        while(iterator.hasNext() && left > 0) {
            iterator.next();
            left--;
        }
        return iterator;
    }

    /**
     * Returns an iterator that iterates over the slice of the given collection starting
     * from {@code from} index (inclusive) to  {@code to} index (exclusive).
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param iterator iterator, not null, not empty
     * @param from index from which to slice the collection. If less than zero, zero is assumed.
     * @param to index to which to slice the collection. If greater than the size of the collection, returns all elements
     * of the collection from the {@code from} index.
     * If {@code to} is less than {@code from}, an empty iterator is returned.
     * @param <E> type of elements in the collection
     * @return the new iterator iterating over all elements of the given iterator starting from {@code from} (inclusive)
     * to {@code to} exclusive.
     * @throws NullPointerException iterator is null
     */
    public static <E> Iterator<E> slice(Iterator<E> iterator, int from, int to) {
        if(to < from) return empty();
        return new TakingIterator<E>(drop(iterator, from), to - from);
    }

    /**
     * Returns a string made by concatenating the elements of the given iterator with the given separator.
     * <p>
     * ToString() is used for the members of collection.
     * @param iterator iterator, not null
     * @param separator to use for elements concatenation
     * @return string representation of all the collection members, concatenated with the given separator
     * @throws NullPointerException iterator is null
     */
    public static <E> String mkString(Iterator<E> iterator, String separator) {
        return Joiner.on(separator).join(iterator);
    }

    /**
     * Returns a string made by concatenating the elements of the given iterator with the given separator.
     * The string has the given postfix and prefix.
     * <p>
     * ToString() is used for the members of collection.
     * @param iterator iterator, not null
     * @param start the prefix
     * @param separator to use for elements concatenation
     * @param end the postfix
     * @return string representation of all the collection members, concatenated with the given separator
     * @throws NullPointerException iterator is null
     */
    public static <E> String mkString(Iterator<E> iterator, String start, String separator, String end) {
        return Joiner.on(separator).join(start, end, iterator);
    }

    /**
     * Returns true if the two given iterators are equal (in terms of <code>equals</code>) - i.e. contain
     * the same number of equal elements in the same order.
     * After this operation the iterators may be advanced to an arbitrary position so it is safer not to use
     * them after this method call.
     * @param it1 first iterator, not null
     * @param it2 second iterator, not null
     * @param <E> type of element
     * @return true if iterators are equal, false otherwise
     * @throws NullPointerException any of the iterators is null
     */
    public static <E> boolean areEqual(Iterator<E> it1, Iterator<E> it2) {
        while(it1.hasNext() && it2.hasNext()) {
            E e1 = it1.next();
            E e2 = it2.next();
            if(e1 == null && e2 != null) return false;
            if(e1 != null && !e1.equals(e2)) return false;
        }
        return !(it1.hasNext() || it2.hasNext());
    }

    /**
     * Returns a new set containing all the elements from the given iterator
     * @param iterator iterator, not null
     * @param <E> type of elements
     * @return a new set. If iterator is exhausted, an empty set is returned
     * @throws NullPointerException iterator is null
     */
    public static <E> Set<E> toSet(Iterator<E> iterator) {
        return foldLeft(iterator, new HashSet<E>(), new Function2<E, HashSet<E>, HashSet<E>>() {
            public HashSet<E> apply(E arg1, HashSet<E> arg2) {
                arg2.add(arg1);
                return arg2;
            }
        });        
    }

    /**
     * Returns a new list containing all the elements from the given iterator
     * @param iterator iterator, not null
     * @param <E> type of elements
     * @return a new list. If iterator is exhausted, an empty list is returned
     * @throws NullPointerException iterator is null
     */
    public static <E> List<E> toList(Iterator<E> iterator) {
        return foldLeft(iterator, new ArrayList<E>(), new Function2<E, ArrayList<E>, ArrayList<E>>() {
            public ArrayList<E> apply(E arg1, ArrayList<E> arg2) {
                arg2.add(arg1);
                return arg2;
            }
        });
    }

    /**
     * Returns an iterator that iterates over all elements of the given array
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param array array, not null
     * @param <E> type of elements
     * @return iterator over all elements in the array
     * @throws NullPointerException array is null
     */
    public static <E> Iterator<E> forArray(E[] array) {
        return Arrays.asList(array).iterator();
    }

    /**
     * Returns an iterator that performs zipping of the given iterators:
     * elements of first iterator become a first element of the pair, elements of the second iterator
     * become the second element of the pair.
     * <p>
     * If the given iterators are of different size, the longest is truncated.
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param iterator1 iterator to serve as first member of the resulting tuples, not null
     * @param iterator2 iterator to serve as second member of the resulting tuples, not null
     * @param <E1> type of elements in the first iterator
     * @param <E2> type of elements in the second iterator
     * @return iterator producing tuples from the given iterators or empty iterator if one of the given
     * iterators is empty
     * @throws NullPointerException any of the given iterators is null
     */
    public static <E1, E2> Iterator<Tuple2<E1, E2>> zip(Iterator<? extends E1> iterator1, Iterator<? extends E2> iterator2) {
        return new ZippingIterator<E1, E2>(iterator1, iterator2);
    }

    /**
     * Returns a new iterator backed up by the given elements in the given order.
     * <p>
     * The returned iterator does not support {@link java.util.Iterator#remove()}.
     * @param values values to iterate over.
     * @param <E> type of element
     * @return the new iterator iterating over the given values or empty iterator if there are no values
     */
    public static <E> Iterator<E> it(E... values) {
        return Arrays.asList(values).iterator();
    }

    private static class FilteringIterator<E>  extends NonModifiableIterator<E> {
        private final Iterator<E> iterator;
        private final Predicate<? super E> predicate;
        private Option<E> buffer = Option.none();

        public FilteringIterator(Iterator<E> iterator, Predicate<? super E> predicate) {
            this.iterator = Argument.requireNotNull(iterator, "iterator");
            this.predicate = Argument.requireNotNull(predicate, "predicate");
        }

        public boolean hasNext() {
            fetchNext();
            return buffer.isSome();
        }

        private void fetchNext() {
            while(buffer.isNone() && iterator.hasNext()) {
                E value = iterator.next();
                if(predicate.apply(value)) {
                    buffer = some(value);
                }
            }
        }

        public E next() {
            fetchNext();
            E value = buffer.get();
            buffer = Option.none();
            return value;
        }

        @Override
        public String toString() {
            return "filteringIterator-" + hashCode();
        }
    }

    private static class MappingIterator<T, R>  extends NonModifiableIterator<R> {

        private final Iterator<T> it;
        private final Function<? super T, ? extends R> f;

        public MappingIterator(Iterator<T> it, Function<? super T,? extends R> f) {
            this.it = Argument.requireNotNull(it, "it");
            this.f = Argument.requireNotNull(f, "f");
        }

        public boolean hasNext() {
            return it.hasNext();
        }

        public R next() {
            return f.apply(it.next());
        }

        @Override
        public String toString() {
            return "mappingIterator-" + hashCode();
        }
    }

    private static class FlatMappingIterator<E, R>  extends NonModifiableIterator<R> {
        private final Iterator<E> it;
        private final Function<? super E, ? extends Collection<R>> f;
        private Option<Iterator<R>> buffer = Option.none();

        public FlatMappingIterator(Iterator<E> it, Function<? super E,? extends Collection<R>> f) {
            this.it = Argument.requireNotNull(it, "it");
            this.f = Argument.requireNotNull(f, "f");
        }

        public boolean hasNext() {
            fetchNext();
            return buffer.isSome() && buffer.get().hasNext();
        }

        private void fetchNext() {
            while(it.hasNext() && (buffer.isNone() || !buffer.get().hasNext())) {
                Iterator<R> iterator = f.apply(it.next()).iterator();
                if(iterator.hasNext()) {
                    buffer = some(iterator);
                }
            }
        }

        public R next() {
            fetchNext();
            Iterator<R> iterator = buffer.get();
            return iterator.next();
        }

        @Override
        public String toString() {
            return "flatMappingIterator-" + hashCode();
        }
    }

    private static class TakingIterator<T> implements Iterator<T> {
        private final Iterator<T> iterator;
        private int left;

        public TakingIterator(Iterator<T> iterator, int count) {
            this.iterator = Argument.requireNotNull(iterator, "iterator");
            this.left = count;
        }

        public boolean hasNext() {
            return left > 0 && iterator.hasNext();
        }

        public T next() {
            if(left <= 0) throw new NoSuchElementException();
            T next = iterator.next();
            left--;
            return next;
        }

        public void remove() {
            iterator.remove();
        }

        @Override
        public String toString() {
            return "takingIterator-" + hashCode();
        }
    }

    private static class EmptyIterator<T> extends NonModifiableIterator<T> {
        public boolean hasNext() {
            return false;
        }

        public T next() {
            throw new NoSuchElementException();
        }

        @Override
        public String toString() {
            return "emptyIterator";
        }
    }

    private static class ZippingIterator<E1, E2> extends NonModifiableIterator<Tuple2<E1, E2>> {
        private final Iterator<? extends E1> iterator1;
        private final Iterator<? extends E2> iterator2;

        public ZippingIterator(Iterator<? extends E1> iterator1, Iterator<? extends E2> iterator2) {
            this.iterator1 = Argument.requireNotNull(iterator1, "iterator1");
            this.iterator2 = Argument.requireNotNull(iterator2, "iterator2");
        }

        public boolean hasNext() {
            return iterator1.hasNext() && iterator2.hasNext();
        }

        public Tuple2<E1, E2> next() {
            return pair(iterator1.next(), iterator2.next()) ;
        }

        @Override
        public String toString() {
            return "zippingIterator-" + hashCode();
        }
    }

    private static class TakingWhileIterator<E> extends NonModifiableIterator<E> {
        private final Iterator<E> iterator;
        private final Predicate<E> predicate;
        private Option<E> buffer = Option.none();
        private boolean finished = false;

        public TakingWhileIterator(Iterator<E> iterator, Predicate<E> predicate) {
            this.iterator = iterator;
            this.predicate = predicate;
        }

        public boolean hasNext() {
            fetchNext();
            return buffer.isSome();
        }

        private void fetchNext() {
           while(!finished && buffer.isNone() && iterator.hasNext()) {
                E value = iterator.next();
                if(predicate.apply(value)) {
                    buffer = some(value);
                } else {
                    finished = true;
                }
            }
        }

        public E next() {
            fetchNext();
            E value = buffer.get();
            buffer = Option.none();
            return value;
        }

        @Override
        public String toString() {
            return "takingWhileIterator-" + hashCode();
        }
    }

    private static class CyclingIterator<E> extends NonModifiableIterator<E> {
        private final Iterable<E> iterable;
        private Iterator<E> it = null;

        public CyclingIterator(Iterable<E> iterable) {
            this.iterable = Argument.requireNotNull(iterable, "iterable");
        }

        public boolean hasNext() {
            fetchNextIterator();
            return it.hasNext();
        }

        public E next() {
            fetchNextIterator();
            return it.next();
        }

        private void fetchNextIterator() {
            if(it == null || !it.hasNext()) {
                it = iterable.iterator();
            }
        }

        @Override
        public String toString() {
            return "cyclingIterator-" + hashCode();
        }
    }

    private static class JoiningIterator<E> extends NonModifiableIterator<E>  {
        private final Iterator<E> it1;
        private final Iterator<E> it2;

        public JoiningIterator(Iterator<E> it1, Iterator<E> it2) {
            this.it1 = requireNotNull(it1);
            this.it2 = requireNotNull(it2);
        }

        public boolean hasNext() {
            return it1.hasNext() || it2.hasNext();
        }

        public E next() {
            return it1.hasNext() ? it1.next() : it2.next();
        }

        @Override
        public String toString() {
            return "joiningIterator-" + hashCode();
        }
    }

    private static class InterleavingIterator<E> extends NonModifiableIterator<E> {
        private final Iterator<Iterator<E>> iterators;
        private Iterator<E> currentIterator = null;

        public InterleavingIterator(Iterator<E>[] iterators) {
            requireNotNull(iterators, "iterators");
            require(iterators.length > 0, "Iterators should not be empty");
            for(Iterator<E> it : iterators) requireNotNull(it);
            this.iterators = cycle(Arrays.asList(iterators));
        }

        public boolean hasNext() {
            fetchNextIterator();
            return currentIterator.hasNext();
        }

        private void fetchNextIterator() {
            if(currentIterator == null) {
                currentIterator = iterators.next();
            }
        }

        public E next() {
            fetchNextIterator();
            E value = currentIterator.next();
            currentIterator = null;
            return value;
        }

        @Override
        public String toString() {
            return "interleavingIterator-" + hashCode();
        }
    }
}